A Ternary Content Addressable Memory (“TCAM”) is a type of computer memory used in certain high speed searching applications, such as routing information through a network. It is designed such that it receives a data word (e.g., a key in a packet header) and performs parallel matches of that word against every entry in the TCAM in a single clock cycle. Each TCAM entry can store a flow rule comprising a key, an action, and a priority.
TCAMs have been widely used in routers, switches, and network security appliances of high speed networks to implement packet flow rules, e.g., access control list (“ACL”) call rules. They may be used for various applications, including packet filtering, forwarding, traffic load balancing and shaping. However, TCAMS may be very costly and may consume a significant amount of power. Accordingly, TCAMs are often small and do not scale well to large networks using thousands of flow rules.
TCAMs are often used in network routers. TCAMs may have variable widths, where the width is inversely proportional to a capacity of the TCAM. For example, a TCAM may support 1000 entries of 72 bits, 512 entries of 144 bits, or 256 entries of 288 bits. Traditionally, a router programs each flow rule (comprising a key, priority, and an action) into one TCAM entry, and configures the width of the TCAM to be the maximum width of flow key. This results in minimal capacity of the TCAM.
Some chip hardware includes a pipeline of tables. The pipeline of tables may be used to perform a multi-stage look-up of packets, in which the result of one table lookup is used as part of lookup key to the next table in the pipeline. For instance, Broadcam chips support a 3-stage pipeline: VFP (Virtual local area network Field Processor), IFP (Ingress Field Processor), and EFP (Egress Field Processor): VFP generates an VRF; (VRF_id, dst_ip, dst_port, . . . ) is matched against IFP, which produces (egress_port, egress_mod_id); (egress_port, src_ip, dst_ip, . . . ) is matched against EFP. Similarly, Dune Networking chips support a 4-stage pipeline: AC classification table (generating VRF_id), LPM (Longest Prefix Match), IFP-stage-1 (using (FEC_id, src_ip, dst_ip, etc.) as the lookup key), IFP-stage-2, and EFP.